package com.likou;

public class q25 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k <= 1) {
            return head;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        ListNode curr = head;

        // 计算链表长度
        int length = 0;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        curr = head;
        // 当剩余节点数大于等于k时才进行反转
        while (length >= k) {
            // 反转k个节点
            ListNode first = curr;
            ListNode prev = null;
            for (int i = 0; i < k; i++) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }

            // 连接反转后的子链表
            pre.next = prev;
            first.next = curr;
            pre = first;

            length -= k;
        }

        return dummy.next;
    }
}
